package exam;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class test8 {
    public static void main(String[] args) {
        int []nums={3,2,1,5,6,4};
        System.out.println(findKthLargest(nums,2));

    }

    int []tmp;
    public int reversePairs(int[] record) {
        int n=record.length;
        tmp=new int[n];
        return mergeSort(record,0,record.length-1);
    }

    public int mergeSort(int []nums,int left,int right){
        if(left>=right)return 0;
        int mid=left+(right-left)/2;
        int ret=0;
        ret+=mergeSort(nums,left,mid);
        ret+=mergeSort(nums,mid+1,right);

        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=right){
            if(nums[cur1]<=nums[cur2]){
                tmp[i++]=nums[cur1++];
            }else{
                ret+=mid-cur1+1;
                tmp[i++]=nums[cur2++];
            }
        }

        while(cur1<=mid)tmp[i++]=nums[cur1++];
        while(cur2<=right)tmp[i++]=nums[cur2++];

        for(int j=left;j<=right;j++){
            nums[j]=tmp[j-left];
        }
        return ret;
    }


    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock,0,stock.length-1,cnt);
        int []ret=new int[cnt];
        for(int i=0;i<cnt;i++){
            ret[i]=stock[i];
        }
        return ret;
    }

    private void qsort(int[]nums,int left,int right,int cnt){
        if(left>=right)return;
        int key=nums[new Random().nextInt(right-left+1)+left];
        int l=left-1,r=right+1,i=left;
        while(i<r){
            if(nums[i]<key){
                swap(nums,++l,i++);
            }else if(nums[i]==key){
                i++;
            }else{
                swap(nums,--r,i);
            }
        }
        int a=l-left+1;
        int b=r-l-1;

        if(cnt<a){
            qsort(nums,left,l,cnt);
        }else if(cnt<=a+b){
            return;
        }else{
            qsort(nums,r,right,cnt-a-b);
        }
    }
    private void swap3(int[]nums,int right,int left){
        int t=nums[left];
        nums[left]=nums[right];
        nums[right]=t;
    }


    public static int findKthLargest(int[] nums, int k) {
        return find(nums,0,nums.length-1,k);
    }

    private static int find(int[]nums,int left,int right,int k){
        if(left==right){
            return nums[left];
        }
        int l=left-1,r=right+1,i=left;
        int key=nums[new Random().nextInt(right-left+1)+left];
        while(i<r){
            if(nums[i]<key){
                swap(nums,++l,i++);
            }else if(nums[i]==key){
                i++;
            }else{
                swap(nums,--r,i);
            }
        }
        int b=r-l-1;
        int c=right-r+1;
        if(c>=k){
            return find(nums,r,right,k);
        }else if(c+b>=k){
            return key;
        }else{
            return find(nums,left,l,k-c-b);
        }
    }

    private static void swap(int[]nums,int left,int right){
        int t=nums[left];
        nums[left]=nums[right];
        nums[right]=t;
    }



    public int[] sortArray(int[] nums) {
        sort(nums,0,nums.length-1);
        return nums;
    }

    private void sort(int []nums,int left,int right){
        if(left>=right){
            return;
        }
        int key=nums[new Random().nextInt(right-left+1)+left];
        int l=left-1,r=right+1,i=left;
        while(i<r){
            if(nums[i]<key){
                swap(nums,++l,i++);
            } else if (nums[i]==key) {
                i++;
            }else {
                swap(nums,--r,i);
            }
        }
        sort(nums,left,l);
        sort(nums,r,right);
    }

    private void swap2(int[]nums,int left,int right){
        int t=nums[left];
        nums[left]=nums[right];
        nums[right]=t;
    }


    public void sortColors(int[] nums) {
        int left=-1,right=nums.length,i=0;
        while(i<right){
            if(nums[i]==0){
                swap1(nums,++left,i++);
            }else if(nums[i]==1){
                i++;
            }else{
                swap1(nums,--right,i);
            }
        }
    }

    private void swap1(int []nums,int left,int right){
        int t=nums[left];
        nums[left]=nums[right];
        nums[right]=t;
    }


    public int minNumberOfFrogs(String croakOfFrogs) {
        char []ch=croakOfFrogs.toCharArray();
        String t="croak";
        int []hash=new int[5];
        Map<Character,Integer>map=new HashMap<>();
        for(int i=0;i<t.length();i++){
            map.put(t.charAt(i),i);
        }

        for(char c:ch){
            if(c==t.charAt(0)){
                if(hash[4]!=0){
                    hash[4]--;
                }
                hash[0]++;
            }else{
                if(hash[map.get(c)-1]==0)return -1;
                hash[map.get(c)-1]--;
                hash[map.get(c)]++;
            }
        }
        for(int i=0;i<hash.length-1;i++){
            if(hash[i]!=0){
                return -1;
            }
        }
        return hash[4];
    }

}
